package com.axzh.interview.leetcode;

public class BestTimeToBuyAndSellStock3 {

	public static void main(String[] args) {
		int[] prices = { 3, 8, 5, 1, 7, 8 };
		System.out.println(BestTimeToBuyAndSellStock3.maxProfit(prices));
	}

	public static int maxProfit(int[] prices) {
		if (prices.length == 0) {
			return 0;
		}
		int[] profit_1 = new int[prices.length];
		profit_1[0] = 0;
		int minPrice = prices[0];
		for (int i = 1; i < prices.length; i++) {
			profit_1[i] = Math.max(profit_1[i - 1], prices[i] - minPrice);
			minPrice = Math.min(minPrice, prices[i]);
		}
		int maxPrice = prices[prices.length - 1];
		int[] profit_2 = new int[prices.length];
		profit_2[prices.length - 1] = 0;
		for (int i = prices.length - 2; i > 0; i--) {
			profit_2[i] = Math.max(profit_2[i + 1], maxPrice - prices[i]);
			maxPrice = Math.max(maxPrice, prices[i]);
		}
		int maxProfit = 0;
		for (int i = 0; i < prices.length; i++) {
			if (profit_1[i] + profit_2[i] > maxProfit) {
				maxProfit = profit_1[i] + profit_2[i];
			}
		}
		return maxProfit;
	}

}
